package com.cbhb.sys;


/**
 * 两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
 *
 * 给出两个整数 x 和 y，计算它们之间的汉明距离。
 *
 * 注意：
 * 0 ≤ x, y < 231.
 *
 * 示例:
 *
 * 输入: x = 1, y = 4
 *
 * 输出: 2
 *
 * 解释:
 * 1   (0 0 0 1)
 * 4   (0 1 0 0)
 *        ↑   ↑
 *
 * 上面的箭头指出了对应二进制位不同的位置。
 */
public class HammingDistance {

    public static int hammingDistance(int x, int y) {
        String sx = Integer.toBinaryString(x);
        String sy = Integer.toBinaryString(y);
        int[] nums = new int[31];
        int sum = 0;
        for (int i = sx.length() -1; i>=0 ; i--) {
            nums[sx.length()-1-i] = (int)sx.charAt(i)-(int)'0';
        }
        for(int i = sy.length() - 1; i>=0 ; i--) {
            if (nums[sy.length()-1-i] != (int)sy.charAt(i)-(int)'0') {
                sum++;
            }
        }
        if (x > y) {
            // x > y时候，并不能完全比较到
            for (int i = sy.length(); i<sx.length();i++) {
                if (nums[i] == 1) {
                    sum++;
                }
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(hammingDistance2(97, 73));
    }

    public static int hammingDistance2(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}
